In fault tree analysis (FTA), a k/n gate is usually converted into a set of k-combinations of its input events for evaluating minimal cut sets (MCSs) in a fault tree. As proposed by NPL 1, the conversion is generally executed by repetitively expanding the k/n gate into sub-voting gates until k=1 or k=n is attained.
However, the space complexity by the expansion (that is, the number of resulting k-combinations) is
      O    ⁡          (              nl                              k            ⁡                          (                              n                -                k                            )                                ⁢          l                    )        ,and in such a case, the problem becomes factorial, which easily results in a memory overflow error in practice when n is relatively large and k is close to n/2.
Further, the problem of the space complexity becomes more serious when an input to a k/n gate is not a basic event but, for example, a disjunction (OR gate) of other events. For example, for a k/n gate in which each input is comprised of a disjunction of 1 events, the space complexity is
      O    ⁡          (                        l          k                ·                  nl                                    k              ⁡                              (                                  n                  -                  k                                )                                      ⁢            l                              )        .